package 树;

import java.util.NoSuchElementException;

public class 基于整形的二分搜索树 {
    private  int size;
    private TreeNode root;

    /**
     * 二分搜索树的添加操作
     * @param val
     */
    public void add(int val){
        root = add(root,val);
    }

    /**
     * 传入根节点和val，就能在树的尾部添加一个节点
     * @param root
     * @param val
     * @return
     */
    private TreeNode add(TreeNode root, int val){
        if (root == null){
            TreeNode node = new TreeNode(val);
            size++;
            return node;
        }
        if ((Integer)root.val > val){
            root.left = add(root.left,val);
        }else {
            root.right = add(root.right,val);
        }
        return root;
    }

    /**
     * s是否包含val的方法
     * @param val
     * @return
     */
    public boolean contains(int val){
        return contains(root,val);
    }

    /**
     * 二分搜索树是否包含val
     * @param root
     * @param val
     * @return
     */
    private boolean contains(TreeNode root, int val) {
        if (root == null){
            return false;
        }
        if ((int) root.val == val){
            return true;
        }
        if ((int)root.val > val){
            return contains(root.left,val);
        }else {
            return contains(root.right,val);
        }
    }

    /**
     * 寻找最小值的方法
     * @return
     */
    public int findMin(){
        if (size == 0){
            throw new NullPointerException("节点为空");
        }
        return (int) min(root).val;
    }

    /**
     * 传入一个根节点，就可以找到树中的最小值
     * @param root
     * @return 返回树的最小值
     */
    private TreeNode min(TreeNode root) {
        if (root.left != null){
            return min(root.left);
        }
        return root;
    }

    /**
     * 最大值方法
     * @return
     */
    public int findMax(){
        if (size == 0){
            throw new NullPointerException("节点为空");
        }
        return (int) max(root).val;
    }

    /**
     * 在树中找到最大值的方法
     * @param root
     * @return
     */
    private TreeNode max(TreeNode root) {
        if (root.right != null){
            return max(root.right);
        }
        return root;
    }

    /**
     * 删除树中最小节点
     * @return
     */
    public int removeMin(){
        if (size == 0){
            throw new NoSuchElementException("数为空，无法删除");
        }
        TreeNode minNode = min(root);
        root.left = removeMin(minNode);
        return (int) minNode.val;
    }

    private TreeNode removeMin(TreeNode root) {
        if (root.left == null){
            TreeNode right = root.right;
            root.left = root.right = root = null;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    /**
     * 删除任意节点
     * @return
     */
    public void remove(int val){
        //节点为空
        if (root == null){
            throw new NoSuchElementException("树为空");
        }
        root = remove(root,val);
    }

    private TreeNode remove(TreeNode root, int val) {
        if ((int)root.val == val) {//如果删除的节点为根节点
            if (root.left == null){
                TreeNode right = root.right;
                root.right = root = null;
                size--;
                return right;
            }
            if (root.right == null){
                TreeNode right = root.left;
                root.left = root = null;
                size--;
                return right;
            }
            //左右子树都不为空，新根节点
            TreeNode cur = min(root.right);
            //删除右子树最小的节点
            cur.right = removeMin(root.right);
            cur.left = root.left;
            root.left = root.right = root = null;
            size--;
            return cur;
        }else if ((int)root.val > val){
            root.left =  remove(root.left,val);
            return root;
        }else {
            root.right = remove(root.right, val);
            return root;
        }
    }

    /**
     * 删除树中最小节点
     * @return
     */
    public int removeMax(){
        if (size == 0){
            throw new NoSuchElementException("数为空，无法删除");
        }
        TreeNode maxNode = max(root);
        root.right = removeMax(maxNode);
        return (int) maxNode.val;
    }

    private TreeNode removeMax(TreeNode root) {
        if (root.right == null){
            TreeNode left = root.left;
            root.left = root.right = root = null;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,sb,0);
        return sb.toString();
    }

    private void generateBSTString(TreeNode root, StringBuilder sb, int height) {
        if (root == null){
            sb.append(generateHeightStr(height)).append("NULL\n");
            return;
        }
        sb.append(generateHeightStr(height)).append(root.val).append("\n");
        generateBSTString(root.left,sb,height+1);
        generateBSTString(root.right ,sb,height+1);
    }

    private String generateHeightStr(int height) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();

    }
}
class Test{
    public static void main(String[] args) {
        基于整形的二分搜索树 o = new 基于整形的二分搜索树();
        o.add(28);
        o.add(16);
        o.add(30);
        o.add(22);
        o.add(29);
//        System.out.println(o.removeMin());
        o.remove(28);
        System.out.println(o.toString());
    }
}
